package tree.huffmanCoding;

import java.io.*;
import java.util.*;

/**
 * 霍夫曼编码的压缩与解压缩   是挺难的哈 涉及到了二进制
 */
public class HuffmanCoding {
    public static void main(String[] args) throws IOException {
        String str = "i like like like java do you like a java";
        // 编码压缩
        byte[] zippedBytes = huffmanZip(str.getBytes());
        byte[] by = str.getBytes();
        ArrayList<CharNode> nodes = strToArrayList(str.getBytes());
        CharNode root = getHuffmanTree(nodes); // 创建霍夫曼树 得到root节点
        Map<Byte, String> huffmanCodes = getHuffmanCharCoding(root); // 获得每个字符霍夫曼编码
        // 解码
        byte[] s= unZip(zippedBytes, huffmanCodes);
        /**
         * 这句话让ascII码转换为字符
         */
        System.out.println(new String(s));
        // 测试压缩文件
        String srcFile = "/Users/jhu/Desktop/rabbit.gif";
        String destFIle = "/Users/jhu/Desktop/rabbit.zip";
        zipFIle(srcFile, destFIle);
        // 测试压缩文件
        String destFIle2 = "/Users/jhu/Desktop/rabbit2.gif";
        unZipFile(destFIle, destFIle2);
    }

    /**
     * 编写一个封装方法
     */
    public static byte[] huffmanZip(byte[] origin) {
        ArrayList<CharNode> nodes = strToArrayList(origin);
        CharNode root = getHuffmanTree(nodes); // 创建霍夫曼树 得到root节点
        Map<Byte, String> huffmanCodes = getHuffmanCharCoding(root); // 获得每个字符霍夫曼编码
        System.out.println("解压前的code");  // 40字节
        System.out.println(origin.length);
        byte[] zippedBytes = zip(origin, huffmanCodes);
        System.out.println("解压的code");
        System.out.println(Arrays.toString(zippedBytes));  // 长度为17字节
        System.out.println(zippedBytes.length);
        System.out.println("解压率为" + (origin.length - zippedBytes.length) / (origin.length + 0.0));
        return zippedBytes;
    }

    /**
     * 将一个String转换为Map, key 为字符对应的字节码，value为出现的次数，作为CharNode的权重
     */
    public static ArrayList<CharNode> strToArrayList(byte[] bytes) {
        HashMap<Byte, Integer> map = new HashMap<>();
        ArrayList<CharNode> nodes = new ArrayList<>();
        for (Byte c : bytes) {
            if (!map.containsKey(c)) {
                map.put(c, 1);
            } else {
                map.put(c, map.get(c) + 1);
            }
        }
        // 遍历Map
        for (Map.Entry<Byte, Integer> element : map.entrySet()) {
            nodes.add(new CharNode(element.getKey(), element.getValue()));
        }
        return nodes;
    }

    /**
     * 生成huffman树，叶子节点data为字节码，权重为次数
     */
    private static CharNode getHuffmanTree(ArrayList<CharNode> nodes) {
        while (nodes.size() > 1) {
            Collections.sort(nodes);
            CharNode left = nodes.get(0);
            CharNode right = nodes.get(1);
            // 新建一个根节点
            CharNode root = new CharNode(null, left.getWeight() + right.getWeight());
            root.setLeft(left);
            root.setRight(right);
            // 删除二个节点
            nodes.remove(left);
            nodes.remove(right);
            // 将跟节点添加进集合中
            nodes.add(root);
        }
        // 返回霍夫曼树的root节点
        return nodes.get(0);
    }

    /**
     * 核心代码 在CharNode中
     */
    public static Map<Byte, String> getHuffmanCharCoding(CharNode node) {
        if (node == null) {
            return null;
        }
        return node.getCharCodingAtHuffmanTree(node, "", new StringBuilder());
    }

    /**
     * 最佳实践 -- 数据压缩压缩压缩压缩压缩压缩压缩压缩压缩压缩压缩压缩压缩压缩压缩压缩
     * <p>
     * 将字符串转为byte数组，通过生成的霍夫曼编码表，返回一个霍夫曼压缩后的byte数组,byte数组中可以放8位二进制数字
     * String content = "i like like like java ···"
     * 返回的霍夫曼字符串为："101010001011111111100100010100011010·····" 我们需要把它转为补码
     * 我们将字符串8位做一个分割，装进byte[],byte（字节，一字节有八位二进制数）再使用Integer.parseInt(str,radix) 转为10进制
     * huffmanCodeBytes[0] = 10101000(补码) ==> 原码:11011000  十进制数为：-88 需要将补码转为原码 补了再补。因为
     * 10101000在计算机传输中都是按照补码的形式传输的。
     * 补码的设计使得二进制减法可以转化成加法，这样CPU只需要设计加法器就行了，不用再专门设计减法器了
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
        StringBuilder sb = new StringBuilder();
        for (byte aByte : bytes) {
            sb.append(huffmanCodes.get(aByte));
        }
        // len表示压缩后字节编码的长度
        int len = 0;
        if (sb.length() % 8 == 0) {
            len = sb.length() / 8;
        } else { // 不能被8整除
            len = sb.length() / 8 + 1;
        }
        // 创建压缩后的byte数组
        byte[] huffmanByte = new byte[len];
        int index = 0;
        for (int i = 0; i < sb.length(); i += 8) {
            String strByte;
            if (i + 8 > sb.length()) {  // 不够8位
                strByte = sb.substring(i);
            } else {
                strByte = sb.substring(i, i + 8);
            }
            // 这句话有点难理解了 意思是将字符串以二进制形式转为十进制整数
            huffmanByte[index++] = (byte) Integer.parseInt(strByte, 2);
        }
        return huffmanByte;

    }

    /**
     * 数据解压
     */
    public static byte[] unZip(byte[] zippedBytes, Map<Byte, String> huffmanCodes) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < zippedBytes.length; i++) {
            boolean flag = (i == zippedBytes.length - 1);
            sb.append(byteToBitString(!flag, zippedBytes[i]));
        }
        // 生成一个反向的霍夫曼表， 因为是解码需要反过来
        HashMap<String, Byte> map = new HashMap<>();
        for (Map.Entry<Byte, String> element : huffmanCodes.entrySet()) {
            map.put(element.getValue(), element.getKey());
        }
        System.out.println(map);
        ArrayList<Byte> list = new ArrayList<>();
        for (int i = 0; i < sb.length(); i++) {
            int count = 1; // 计数器
            boolean flag = true;
            Byte b = null;
            while (flag) {
                String key = sb.substring(i, i + count);
                b = map.get(key);
                if (null == b) {
                    count++;
                } else {
                    flag = false;
                }
            }
            list.add(b);
            i += count - 1;
        }
        byte[] res = new byte[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    /**
     * 将一个byte转为一个二进制的字符串
     */
    public static String byteToBitString(boolean flag, byte b) {
        int temp = b;
        if (flag) {
            temp |= 256;  // 按位与 正数的补码是不变的 0000 0001 ｜ 1 0000 0000 = 1 0000 00001
        }
        String str = Integer.toBinaryString(temp);
        if (flag) {
            return str.substring(str.length() - 8); // 从倒数第8位开始截取
        } else {
            return str; // 最后几位不满8位 直接返回
        }
    }

    /**
     * 压缩文件
     *
     * @param srcFile  源文件
     * @param destFile 压缩后存放位置
     * @throws IOException
     */
    public static void zipFIle(String srcFile, String destFile) throws IOException {
        // 创建文件输入流
        FileInputStream in = new FileInputStream(srcFile);
        //创建一个和原文件大小一样的byte数组
        byte[] by = new byte[in.available()];
        // 读取文件，将文件保存到byte数组中
        in.read(by);
        //获取到文件对应的霍夫曼表
        byte[] huffmanBytes = huffmanZip(by); // 获得解压后的byte数组

        //创建文件输出流
        OutputStream os = new FileOutputStream(destFile);
        // 创建一个和流相关联的ObjectOutPutStream
        ObjectOutputStream oos = new ObjectOutputStream(os);
        // 以对象流的方式写入霍夫曼编码，为了我们恢复源文件时使用
        oos.writeObject(huffmanBytes);
        ArrayList<CharNode> nodes = strToArrayList(by);
        CharNode root = getHuffmanTree(nodes); // 创建霍夫曼树 得到root节点
        Map<Byte, String> huffmanCodes = getHuffmanCharCoding(root); // 获得霍夫曼编码表 即🔑
        // 同时也得把霍夫曼表写进去  不然怎么解压
        oos.writeObject(huffmanCodes);
        in.close();
        oos.close();
        os.close();
    }

    /**
     * 解压文件 jdk7 try-with-resource写法
     */
    public static void unZipFile(String scrFile, String destFile) {
        try (
                FileInputStream in = new FileInputStream(scrFile);
                // 定义一个文件输出流
                FileOutputStream os = new FileOutputStream(destFile);
                // 定义一个对象输出流
                ObjectInputStream oos = new ObjectInputStream(in)
        ) {
            byte[] huffmanBytes =(byte[]) oos.readObject();
            Map<Byte,String> map = (Map<Byte,String>)oos.readObject();
            byte[] bytes = unZip(huffmanBytes, map);
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}
